package leetcode_day._2021._202108._1120;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/14 22:10
 * 统计不开心的朋友
 * 算法：模拟
 * 按照题目的要求来
 * 遍历每一个朋友，如果 ta 匹配的朋友 x 是该 preferences 中的第一个，那 ta 就是开心的
 * 反之，要遍历 preferences 中 x 之前的所有朋友，然后根据条件判断
 */
public class _14_1583 {
    public static void main(String[] args) {
        int[][] preferences = {{1, 2, 3}, {3, 2, 0}, {3, 1, 0}, {1, 2, 0}};
        int[][] pairs = {{0, 1}, {2, 3}};
        System.out.println(new _14_1583().unhappyFriends(4, preferences, pairs));
    }

    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        Map<Integer, Integer> map = new HashMap<>(n);
        for (int i = 0; i < pairs.length; i++) {
            map.put(pairs[i][0], pairs[i][1]);
            map.put(pairs[i][1], pairs[i][0]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (map.get(i) != preferences[i][0])
                if (checkHappy(i, preferences, map)) ++ans;
        }
        return ans;
    }
    public boolean checkHappy(int x, int[][] preferences, Map<Integer, Integer> map) {
        int y = map.get(x);
        for (int i = 0; i < preferences[x].length; i++) {
            int u = preferences[x][i];
            if (u == y) break;
            // 在 u 中的 preferences 找 x 和 map.get(u)
            int v = map.get(u);
            int a = preferences.length, b = preferences.length;
            for (int j = 0; j < preferences[u].length; j++) {
                int cur = preferences[u][j];
                if (cur == x) a = j;
                if (cur == v) b = j;
            }
            if (a < b) return true;
        }
        return false;
    }

}
